1. Field of the Invention
The present invention relates to a method for processing information by using the method for representing rational expression which is effective for solving simultaneous algebraic equations and so on.
2. Description of the Related Art
Recently, the use of a expression processing system has been practical in order to solve scientific and engineering problems. The high-accuracy in solving simultaneous equations including linear equations is fundamental in the expression processing system which processes expression. Increasing the accuracy is an important factor which improves the performance of the whole system.
In the expression processing system, the Grobner basis has been used as a general solver for solving simultaneous algebraic equations. However, sometimes it happens that the resultant coefficient becomes quite large amount.
This phenomenon is most pronounced in an equation in which the number of solutions is finite. As a result of this, the calculational volume of Grobner basis becomes so large temporally and spatially.
Since the calculational volume becomes so large temporally and spatially, the processing time for information processing using the Grobner basis becomes longer and the rate of occupying memory is increased, with the result that the information processing at high efficiency is impossible.
Therefore, the following representation of solutions by rational expressions is considered to be effective in compensating for the drawback.
In case of the Grobner basis, the solutions of the equation are represented by: EQU f.sub.1 (x.sub.1)=0, x.sub.2 =f.sub.2 (x.sub.1), . . . , x.sub.n =f.sub.n (x.sub.1)
(all of "f" are polynomial.). PA1 f.sub.1 (x.sub.1)=0, x.sub.2 =g.sub.2 (x.sub.1)/f'.sub.1 (x.sub.1), . . . , x.sub.n =g.sub.n (x.sub.1)/f'.sub.1 (x.sub.1) PA1 (all of "f'.sub.1 (x.sub.1)" are differential of polynomial "f.sub.1 (x.sub.1)".). PA1 1) When the number N of the solutions is large, the time and memory required for calculating N.sup.2 normal forms are increased. PA1 2) While the number of the normal forms to be really calculated can be reduced by various ideas, the time and memory required for calculating the aforementioned table are rapidly increased when N is large. PA1 3) Because the order of calculations is important to increase the calculating efficiency, it is difficult that the calculations are made in parallel. PA1 4) Furthermore, it is not assured that the resultant solutions represent all of the solutions. PA1 1-1. choosing a term order O.sub.1 for facilitating the calculation of the Grobner basis; PA1 1-2. calculating the Grobner basis G.sub.1 of F with regard to O.sub.1 ; PA1 1-3. calculating the minimum polynomial f.sub.1 (x.sub.1) based on G.sub.1, the minimum polynomial f.sub.1 (x.sub.1) being a polynomial having the minimum degree of the variable x.sub.1 ; and PA1 1-4. when it is decided that the degree of f.sub.1 (x.sub.1) is equal to the number of solutions given from G.sub.1, PA1 1-5. controlling the digital processor to find solutions represented by rational expressions that is, PA1 {f.sub.1 (x.sub.1)=0, x.sub.2 =f.sub.2 (x.sub.1)/f'.sub.1 (x.sub.1), . . . , x.sub.n =f.sub.n (x.sub.1)/f'.sub.1 (x.sub.1)} [notes: f'.sub.1 (x.sub.1) is differential of f.sub.1 (x.sub.1).]. PA1 2-1. selecting a prime number p which does not divide any head coefficient of all elements of (G.sub.1) and assuming .phi.p as an operation of replacing the coefficient by the remainder regarding the prime number p; PA1 2-2. obtaining the minimum polynomial f.sub.1 (x.sub.1) of x.sub.1 obtained by .phi.p (G.sub.1), regarding p as the modulus; PA1 2-3. obtaining a one-variable polynomial f.sub.1 (x.sub.1) in which the degree is equal to f.sub.1 by replacing the coefficients of f.sub.1 (x.sub.1) by undetermined coefficients to calculate normal forms given by G.sub.1 and eliminating the coefficients to solve linear equations with regard to the undetermined coefficients; PA1 3-1. selecting a prime number p which does not divide any head coefficient of all elements of (G.sub.1) and assuming (p as an operation of replacing the coefficient by the remainder regarding the prime number p; PA1 3-2. calculating Grobner basis G.sub.2 with regard to the lexicographical order of .phi.p (G.sub.1); PA1 3-3. obtaining a one-variable polynomial f.sub.1 (x.sub.1) by calculating normal forms given by G.sub.1 of difference between f'.sub.1 (x.sub.1) x.sub.i and the normal form of f'.sub.1 (x.sub.1) x.sub.i given by G.sub.2 in which the coefficients are replaced by undetermined coefficients in given by G.sub.1 for every i (i=2, . . . , n) and eliminating the coefficients to solve linear equations with the undermined coefficients; PA1 3-4. returning a rational expression: {f.sub.1 (x.sub.1)=0, x.sub.2 =f.sub.2 (x.sub.1)/f'.sub.1 (x.sub.1), . . . , x.sub.n =f.sub.n (x.sub.1)/f'.sub.1 (x.sub.1)} as the solutions; and PA1 3-5. repeating steps 3-2 through 3-4 re-selecting p selected in the step 3-1 when any one of the linear equations can not be solved. PA1 5-1. selecting a prime number p which does not divide any head coefficient of all elements of (G.sub.1) and assuming .phi.p as an operation of replacing the coefficient by the remainder regarding the prime number p; PA1 5-2. calculating Grobner basis G.sub.2 with regard to the term order O of .phi.p (G.sub.1); PA1 5-3. finding an integral coefficient polynomial f.sub.h for each element h of G.sub.2 of which the head coefficient is not divisible by p and the number of head terms coincide with the domain of h; PA1 5-4. when the integral coefficient polynomials f.sub.h are found for all of the elements h of G.sub.2, outputting the whole of f.sub.h as Grobner basis of the integral polynomial set F with regard to the term order O; and PA1 5-5. when any one of the integral coefficient polynomials f.sub.h is not found, re-selecting p selected in said step 5-1 and controlling the digital processor to repeat the steps 5-2 through 5-4 to generate the Grobner basis. PA1 7-1. first of all, calculating Grobner basis in the modulus p; PA1 7-2. storing a history about members and terms in which the elimination was executed and pairs normalized to O, during normalizing .phi.(P) in this process; PA1 7-3. calculating the Grobner basis on rational number based on the history of the foregoing paragraph, at this stage, not executing the normalization on the rational number in relation to the pairs normalized to O in the modulus p, but executing the normalization on the rational number based on the history in relation to pairs normalized to polynomial which is not O in the modulus p, PA1 7-4. returning "nil" assuming that the method of selecting p is not appropriate, when the normalization on the rational number does not correspond to the normalization in the modulus p. f.sub.h in the step 5-3 can be found by replacing coefficients of elements of G.sub.2 by undetermined coefficients to calculate normal forms given by G.sub.1 and eliminating the coefficients to solve linear equations with regard to the undetermined coefficients.
In case of the representation of rational expression, the solutions are represented by:
In finding the solutions of the given equation, once f.sub.1 (x.sub.1)=0 is solved, other variables may be obtained by the substitution. Therefore, the above expressions are considered as the same each other.
The advantage of the representation of rational expression is that the coefficient of g.sub.i is almost remarkably smaller than the coefficient of f.sub.i. As a result of this, there is a possibility of reducing the time and the memory required for finding g.sub.i as compared with f.sub.i.
When using the obtained solutions in the information processing, the common difference increases as coefficient becomes greater. To avoid increase in common difference, it is necessary to solve the f.sub.1 (x.sub.1) at quite high accuracy. Using the representation of rational expression makes the coefficients smaller i.e. the result will be small value, thereby also making the common difference smaller. At the same time, the calculational load is reduced, thereby speeding up the information processing.
A method using the character of the symmetric expressions is proposed as one of methods for finding solutions of this type. In this method, when the number of the solutions is N, a table is made by calculating normal forms of N.sup.2 monomials {.OMEGA..sub.k .OMEGA..sub.1 } relative to the tabulation of N monomials {.OMEGA..sub.k }. On the basis of the table, the trace of powers of matrix is calculated. Finally, f.sub.i and g.sub.i are calculated by forming characteristic polynomials of the matrix.
Though the representation of solutions by rational expressions is possible according to the method as mentioned above, there are, in practice, problems as follows.